﻿#include "BinaryTree_Seq.h"

//创建一个树节点
//参数1：父节点所在数组下标，参数2：标记所创建的是树根、左孩子、右孩子，参数3：插入的树节点的元素值
//返回值，返回存储位置对应的数组下标，返回-1表示非法下标（执行失败）
template <typename T>
int BinaryTree<T>::CreateNode(int parindex, ECCHILDSIGN pointSign, const T& e)
{
	if (pointSign != E_Root) //非根节点，则一定是子节点，要求parindex一定要是个合理值
	{
		if (ifValidRangeIdx(parindex) == false) //位置不合理
			return -1;
		if (SqBiTree[parindex].isValid == false) //父节点不可以无效
			return -1;
	}

	int index = -1;
	if (pointSign == E_Root) //根
	{
		index = 1;//根节点固定存储在下标为1的位置。
	}
	else if (pointSign == E_ChildLeft) //左孩子
	{
		//创建的是左孩子节点，节点i的左孩子节点的下标是2i
		index = 2 * parindex;
		if (ifValidRangeIdx(index) == false)
			return -1; //非法下标
	}
	else //右孩子
	{
		//节点i的右孩子节点的下标是2i+1
		index = 2 * parindex + 1;
		if (ifValidRangeIdx(index) == false)
			return -1; //非法下标
	}

	SqBiTree[index].data = e;
	SqBiTree[index].isValid = true; //标记该下标中有有效数据
	return index;
}

//获取父节点的下标
template <typename T> 
int BinaryTree<T>::getParentIdx(int sonindex)
{
	if (ifValidRangeIdx(sonindex) == false) //位置不合理
		return -1;

	if (SqBiTree[sonindex].isValid == false) //不是个合理的节点，不要尝试找父节点
		return -1;

	return  int(sonindex / 2);  //i的父节点是（i / 2）向下取整
}

//获取某个节点所在的高度：
//根据二叉树性质五：具有n（n > 0）个节点的完全二叉树的高度为⌈log(⁡n + 1)⌉或者⌊log(⁡n)⌋ + 1。这里的对数都是以2为底
template <typename T>
int BinaryTree<T>::getPointLevel(int index)
{
	if (ifValidRangeIdx(index) == false) //位置不合理
		return -1;

	if (SqBiTree[index].isValid == false)//不是个合理的节点，不要尝试找父节点
		return -1;

	//采用公式⌊log(n)⌋ + 1
	int level = int(log(index) / log(2) + 1);//c++中的log（n）函数求的是以e(2.71828)为底的对数值，如果要求以数字m为底的对数值，则需要log(n)/log(m)

	return level;
}

//获取二叉树的深度
template <typename T>
int BinaryTree<T>::getLevel()
{
	if (SqBiTree[1].isValid == false) //没根？
		return 0;

	int i;
	for (i = MaxSize; i >= 1; --i)
	{
		if (SqBiTree[i].isValid == true) //找到最后一个有效节点
			break;
	} //end for
	return getPointLevel(i);
}

//判断是否是个完全二叉树
template <typename T>
bool BinaryTree<T>::ifCompleteBT()
{
	if (SqBiTree[1].isValid == false) //没根？这是二叉树吗？
		return false;

	int i;
	for (i = MaxSize; i >= 1; --i)
	{
		if (SqBiTree[i].isValid == true) //找到最后一个有效节点
			break;
	} //end for

	for (int k = 1; k <= i; ++k)
	{
		if (SqBiTree[k].isValid == false) //所有节点必须都要有效
			return false;
	}
	return true;
}

//前序遍历二叉树，其他的遍历方式在二叉树的链式存储中再详细书写代码和讲解
template <typename T>
void BinaryTree<T>::PreOrderTraversal()
{
	if (SqBiTree[1].isValid == false) //没根？这是二叉树吗？
		return;

	preOrder(1); //根节点的数组下标是1，所以这里把根的下标传递过去
}




